package tulingxueyuan117;

/**
 * Author: Zhang Dongwei
 * Date: 2022/4/6 21:44
 * 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
 *
 */

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
public class p11_合并两个有序链表_21 {

    public static class ListNode{
        int val;
        ListNode next;
        ListNode(){}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    public static void main(String[] args) {
//        ListNode l1 = new ListNode(1);
//        ListNode l2 = l1;
//        for (int i = 2; i < 10; i++) {
//            ListNode listNoden = new ListNode(i);
//            l1.next = listNoden;
//            l1 = l1.next;
//        }
//        l1 = l2;
//
//        ListNode l3 = new ListNode(10);
//        ListNode l4 = l3;
//        for (int i = 11; i < 20; i++) {
//            ListNode listNoden = new ListNode(i);
//            l3.next = listNoden;
//            l3 = l3.next;
//        }
//        l3 = l4;
//
//        System.out.println("=========");
//        while (l1!=null){
//            System.out.println(l1.val);
//            l1 = l1.next;
//        }
//        System.out.println("===============");


        ListNode listNode = new ListNode(0);
        ListNode listNode1 = new ListNode(1);
        ListNode listNode2 = new ListNode(2);

        ListNode listNode3 = new ListNode(3);
        ListNode listNode4 = new ListNode(4);
        ListNode listNode5 = new ListNode(5);
        listNode.next = listNode1;
        listNode1.next = listNode2;

        listNode3.next = listNode4;
        listNode4.next = listNode5;
//        ListNode result = mergeTwoLists(l1, l3);
        ListNode result = mergeTwoLists(listNode, listNode3);
        while (result != null){
            System.out.println(result.val);
            result = result.next;
        }
    }
    // 循环+双指针解决
    public static ListNode mergeTwoLists(ListNode list1, ListNode list2){
        if(list1 == null) return list2;
        if(list2 == null) return list1;
        ListNode resultNode = new ListNode(0);
        ListNode p = resultNode;
        while (list1 != null && list2 != null){
            if(list1.val < list2.val){
                p.next = list1;
                list1 = list1.next;
            }else {
                p.next = list2;
                list2 = list2.next;
            }
            p = p.next;
        }
        if(list1 != null) p.next = list1;
        if(list2 != null) p.next = list2;
//        System.out.println("pstart===========");
//        while (p != null){
//            System.out.println(p.val);
//            p = p.next;
//        }
//        System.out.println("pend=============");
//        System.out.println("resultnodestart===========");
//        while (resultNode != null){
//            System.out.println(resultNode.val);
//            resultNode = resultNode.next;
//        }
//        System.out.println("resultnodestart=============");
        return resultNode.next;
    }
    // 递归解决
    public ListNode mergeTwoLists1(ListNode list1, ListNode list2) {
        if(list1 == null) return list2;
        if(list2 == null) return list1;
        ListNode head = null;
        if(list1.val <= list2.val){
            head = list1;
            head.next = mergeTwoLists(list1.next, list2);
        }else {
            head = list2;
            head.next = mergeTwoLists(list1, list2.next);
        }
        return head;
    }
}
